//
//  Problem714.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 714. 买卖股票的最佳时机含手续费
 给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
 返回获得利润的最大值。
 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

 示例 1:
     输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
     输出: 8
     解释: 能够达到的最大利润:
     在此处买入 prices[0] = 1
     在此处卖出 prices[3] = 8
     在此处买入 prices[4] = 4
     在此处卖出 prices[5] = 9
     总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
 注意:
     0 < prices.length <= 50000.
     0 < prices[i] < 50000.
     0 <= fee < 50000.
 */
@objcMembers class Problem714: NSObject {
    func solution() {
        print(maxProfit([1, 3, 2, 8, 4, 9],  2))
        print(maxProfitClearAlloc([1, 3, 2, 8, 4, 9],  2))
        
        print(maxProfit([1, 10, 4, 3,1, 10, 2, 8, 4, 9],  4))
        print(maxProfitClearAlloc([1, 10, 4, 3,1, 10, 2, 8, 4, 9],  4))
    }
    
    /*
     动态规划：
     1: 创建一个2维数组dp[2][len]
     2: dp[0][i]手里没有股票的最大值：max(昨天也没有股票，昨天有股票今天卖了) = max(dp[0][i-1], dp[1][i-1] + price[i])
        dp[1][i]手里有股票的最大值：max(昨天也没有股票,今天买了，昨天有股票，今天不变) = max(dp[0][i-1] + price[i], dp[1][i-1])
     */
    func maxProfit(_ prices: [Int], _ fee: Int) -> Int {
        if prices.count <= 0 {
            return 0
        }
        
        var dp = Array(repeating: Array(repeating: 0, count: prices.count + 1), count: 2)
        dp[1][0] = Int.min
        for i in 1...prices.count {
            dp[0][i] = max(dp[0][i-1], dp[1][i-1] + prices[i-1])
            dp[1][i] = max(dp[0][i-1] - fee - prices[i-1], dp[1][i-1])
        }
        
        print(dp)
        return dp[0][prices.count]
    }
    
    /*
     优化：
     dp[i]只与dp[i-1]有关
     */
    func maxProfitClearAlloc(_ prices: [Int], _ fee: Int) -> Int {
        if prices.count <= 0 {
            return 0
        }
        
        var last0 = 0
        var last1 = Int.min
        for i in 1...prices.count {
            let temp = max(last0, last1 + prices[i-1])
            last1 = max(last0 - fee - prices[i-1], last1)
            last0 = temp
        }
        
        return last0
    }
}
